package com.leetcode.蓝桥杯.十一届国赛;

/**
 * 小蓝有一条玩具蛇，一共有16节，上面标着数字1至16。每一节都是一个正方形的形状。相令邻的两节可以成直线或者成90度角。
小蓝还有一个4×4的方格盒子，用于存放玩具蛇，盒子的方格上依次标着字母A到Р共16个字母。
小蓝可以折叠自己的玩具蛇放到盒子里面。他发现，有很多种方案可以将玩具蛇放进去。
请帮小蓝计算一下，总共有多少种不同的方案。如果两个方案中，存在玩具蛇的某—节放在了盒子的不同格子里，则认为是不同的方案。

思路：典型的dfs
 * @author LZF
 *
 */
public class 填空题5 {
	static long ans = 0;
	public static void main(String[] args) {
		int[][] p = new int[4][4];
		boolean[][] visit = new boolean[4][4];
		for(int i = 0;i < 4;i++) {
			for(int j = 0;j < 4;j++) {
				visit[i][j] = true;
				dfs(1,p,visit,i,j);
				visit[i][j] = false;
			}
		}
		System.out.println(ans);
		
	}
	public static void dfs(int cur,int[][] p,boolean[][] visit,int x,int y) {
		if(cur == 16) {
			ans++;
		}
		//上
		if(x - 1 >= 0 && !visit[x - 1][y]) {
			visit[x - 1][y] = true;
			dfs(cur + 1,p,visit,x - 1,y);
			visit[x - 1][y] = false;
		}
		//下
		if(x + 1 < 4 && !visit[x + 1][y]) {
			visit[x + 1][y] = true;
			dfs(cur + 1,p,visit,x + 1,y);
			visit[x + 1][y] = false;
		}
		//左
		if(y - 1 >= 0 && !visit[x][y - 1]) {
			visit[x][y - 1] = true;
			dfs(cur + 1,p,visit,x,y - 1);
			visit[x][y - 1] = false;
		}
		//右
		if(y + 1 < 4 && !visit[x][y + 1]) {
			visit[x][y + 1] = true;
			dfs(cur + 1,p,visit,x,y + 1);
			visit[x][y + 1] = false;
		}
	}
}
